package problems.daily;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 1172.餐盘栈
 * <p>https://leetcode.cn/problems/dinner-plate-stacks/</p>
 *
 * @author dubulingbo, 2023/04/28, 028 14:21.
 */
public class DT1172 {
    public static void main(String[] args) {
        System.out.println(0 % 2);
    }
}


class DinnerPlates {
    // 存放数据
    List<Integer> data = new ArrayList<>();
    // data 数组的实际容量
    int size;
    // 表示每个栈的元素数量
    int[] stCnt = new int[100001];
    // 存储出栈元素的下标
    PriorityQueue<Integer> poppedIndexes = new PriorityQueue<>();
    // 每个栈的容量
    final int capacity;

    public DinnerPlates(int capacity) {
        this.capacity = capacity;
        this.size = 0;
    }

    public void push(int val) {
        // 找到第一个没有满的栈
        

        if (poppedIndexes.isEmpty()) {
            // 前 n - 1 个栈都是满的
            int pos = data.size();
            data.add(val);
            // 最后一个栈已满，需要新建一个栈
//            if (pos % capacity == 0) {
//                top.add(0);
//            } else {
//                // 更新最后一个栈的栈顶位置
//                int stackNo = top.size() - 1;
//                top.set(stackNo, top.get(stackNo) + 1);
//            }
        } else {
            // 获取已出栈元素的最小下标
            int i = poppedIndexes.poll();
            data.set(i, val);
//            // 插入的是哪个栈
//            int stackNo = i / capacity;
//            // 对应栈的栈顶指针+1
//            top.set(stackNo, top.get(stackNo) + 1);
        }
    }

    public int pop() {
        // 还没有任何元素入栈
        if (size < 1) return -1;
        // 最后一个栈的编号
        int last = size % capacity != 0 ? size / capacity : size / capacity - 1;
        while (last >= 0 && stCnt[last] < 1) --last;

        // 所有栈都已经为空
        if (last < 0) return -1;

        // 获取编号为last的栈的栈顶元素下标
        // 收缩 data 数组
        size = last * capacity + stCnt[last] - 1;
        --stCnt[last];
        return data.get(size);
    }

    public int popAtStack(int index) {
        if (index < 0 || index >= stCnt.length || stCnt[index] < 1) return -1;

        --stCnt[index];
        // 栈的编号 -> 该栈的栈顶元素所在 data 中的序号
        index = index * capacity + stCnt[index] - 1;
        return data.get(index);
    }
}

/**
 * Your DinnerPlates object will be instantiated and called as such:
 * DinnerPlates obj = new DinnerPlates(capacity);
 * obj.push(val);
 * int param_2 = obj.pop();
 * int param_3 = obj.popAtStack(index);
 */
